<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="Bl9QT" id="Bl9QT"><span data-lake-id="u6a4fbc4c" id="u6a4fbc4c">典型回答</span></h1>
  <p data-lake-id="uc6b7cd2b" id="uc6b7cd2b"><br></p>
  <p data-lake-id="u52b98723" id="u52b98723"><span data-lake-id="u76e9c249" id="u76e9c249">10位数字的QQ号，想要去重，又不给那么多的空间，该如何实现呢？</span></p>
  <p data-lake-id="uc6325e97" id="uc6325e97"><span data-lake-id="u117396a1" id="u117396a1">​</span><br></p>
  <p data-lake-id="u0e84f669" id="u0e84f669"><span data-lake-id="ud974cd6b" id="ud974cd6b">40亿个</span><span data-lake-id="u50a7453d" id="u50a7453d" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">unsigned int，如果直接用内存存储的话，需要：</span></p>
  <p data-lake-id="ufc96408f" id="ufc96408f"><span data-lake-id="u593c5053" id="u593c5053" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">​</span><br></p>
  <p data-lake-id="ue08723f9" id="ue08723f9"><span data-lake-id="u692812d3" id="u692812d3" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">4*4000000000 /1024/1024/1024 = 14.9G ，考虑到其中有一些重复的话，那1G的空间也基本上是不够用的。</span></p>
  <p data-lake-id="uedd08387" id="uedd08387"><span data-lake-id="u7dc655be" id="u7dc655be" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">​</span><br></p>
  <p data-lake-id="uc38c5cd9" id="uc38c5cd9"><span data-lake-id="u8a283097" id="u8a283097" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">想要实现这个功能，可以借助位图。</span></p>
  <p data-lake-id="ucee6439d" id="ucee6439d"><span data-lake-id="u9a0b90b9" id="u9a0b90b9" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">​</span><br></p>
  <p data-lake-id="uf03d5a61" id="uf03d5a61"><br></p>
  <p data-lake-id="u4859d6bd" id="u4859d6bd"><span data-lake-id="u184c9f45" id="u184c9f45" class="lake-fontsize-12">使用位图的话，一个数字只需要占用1个bit，那么40亿个数字也就是：</span></p>
  <p data-lake-id="ud1a99dd1" id="ud1a99dd1"><span data-lake-id="ua5ce13c2" id="ua5ce13c2" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">​</span><br></p>
  <p data-lake-id="u548aef3a" id="u548aef3a"><span data-lake-id="u8c7df081" id="u8c7df081" class="lake-fontsize-12" style="color: rgb(51, 51, 51)">4000000000 * 1 /8 /1024/1024 = 476M </span></p>
  <p data-lake-id="uea7f7664" id="uea7f7664"><span data-lake-id="u8ad363d3" id="u8ad363d3" class="lake-fontsize-12">​</span><br></p>
  <p data-lake-id="ue7d1169b" id="ue7d1169b"><span data-lake-id="uf2f34fcc" id="uf2f34fcc" class="lake-fontsize-12">相比于之前的14.9G来说，大大的节省了很多空间。</span></p>
  <p data-lake-id="uca77ede3" id="uca77ede3"><span data-lake-id="u2dc39170" id="u2dc39170" class="lake-fontsize-12">​</span><br></p>
  <p data-lake-id="u05ee64f9" id="u05ee64f9"><span data-lake-id="ubf8f8599" id="ubf8f8599" class="lake-fontsize-12">比如要把我的QQ号"907607222"放到Bitmap中，就需要找到第907607222这个位置，然后把他设置成1就可以了。</span></p>
  <p data-lake-id="ub0fbf2bf" id="ub0fbf2bf"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1684395974291-6ec45458-da3a-4f69-82d8-3b86927fb386.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_24%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="ud45b7bc0" id="ud45b7bc0"><br></p>
  <p data-lake-id="ue9c35b1b" id="ue9c35b1b"><span data-lake-id="u6eed5484" id="u6eed5484">这样，把40亿个数字都放到Bitmap之后，所有位置上是1的表示存在，不为1的表示不存在，相同的QQ号只需要设置一次1就可以了，那么，最终就把所有是1的数字遍历出来就行了。</span></p>
 </body>
</html>